﻿#define _CRT_SECURE_NO_WARNINGS
// ↑ 将本行在代码放在第一行可以避免 scanf的报错问题（仅在VS编译器里）
//【初阶】44.1 双向循环链表收尾
//【初阶】44.2 双向循环链表收尾+栈和队列
//【初阶】44.3 栈和队列


//【头文件包含】
#include"DoubleList.h"
#include"Stack.h"

//【函数声明】
void DoubleListTest1();
void StackTest1();
/*OJ题-有效的括号判断*/bool JudgeBracket(char* arr);
/*OJ题-有效的括号判断-测试用例*/void JudgeTest();

//【主函数】
int main()
{
	DoubleListTest1();
	StackTest1();
	JudgeTest();
	return 0;
}

//【函数】
/*双向链表测试用例*/void DoubleListTest1()
{
	printf("****双向链表测试用例1开始********************\n");

	DBLN* plist = NULL;
	printf("1.初始化\n");
	plist= DoubleListInit(plist);
	printf("2.尾插1,2,3,4,5\n");
	DoubleListPushBack(plist, 1);
	DoubleListPushBack(plist, 2);
	DoubleListPushBack(plist, 3);
	DoubleListPushBack(plist, 4);
	DoubleListPushBack(plist, 5);
	DoubleListPrint(plist);
	printf("3.尾删1次\n");
	DoubleListPopBack(plist);
	DoubleListPrint(plist);
	printf("4.头插6,7,8\n");
	DoubleListPushFront(plist, 6);
	DoubleListPushFront(plist, 7);
	DoubleListPushFront(plist, 8);
	DoubleListPrint(plist);
	printf("5.尾删2次\n");
	DoubleListPopFront(plist);
	DoubleListPopFront(plist);
	DoubleListPrint(plist);
	printf("6.查询值为3的节点\n");
	DBLN* ret=DoubleListNodeSearch(plist, 3);
	printf("ret=%d\n", ret->data);
	printf("7.从上查到的节点值位置插入5\n");
	DoubleListInsert(ret, 5);
	DoubleListPrint(plist);
	printf("8.删除从上查到的节点值位置\n");
	DoubleListErase(ret);
	DoubleListPrint(plist);
	printf("9.链表空间销毁\n");
	DoubleListesDestroy(plist);
	plist = NULL;

	printf("****双向链表测试用例1结束********************\n\n\n");

}
/*栈测试用例*/void StackTest1()
{
	printf("****栈测试用例1开始********************\n");

	Stk stk1;
	printf("1.初始化\n");
	StackInit(&stk1);
	printf("2.插入数据1,2,3,4,5\n");
	StackPush(&stk1, 1);
	StackPush(&stk1, 2);
	StackPush(&stk1, 3);
	StackPush(&stk1, 4);
	StackPush(&stk1, 5);
	StackPrint(&stk1);
	StackPrintTop(&stk1);
	printf("3.栈顶数据删除1次\n");
	StackPop(&stk1);
	StackPrint(&stk1);
	printf("4.栈顶数据提取\nTOP = [%d]\n", StackTop(&stk1));
	printf("5.栈空判断\n");
	if (StackEmpty(&stk1) == true)printf("Empty\n");
	else printf("NonEmpty\n");
	printf("6.栈大小计算\nSIZE = %d\n", StackSize(&stk1));
	printf("7.栈顶数据删除4次\n");
	StackPop(&stk1);
	StackPop(&stk1);
	StackPop(&stk1);
	StackPop(&stk1);
	printf("8.栈空判断\n");
	if (StackEmpty(&stk1) == true)printf("Empty\n");
	else printf("NonEmpty\n");
	printf("9.栈空间销毁\n");
	StackDestroy(&stk1);

	printf("****栈测试用例1结束********************\n\n\n");

}
/*OJ题-有效的括号判断-函数*/bool JudgeBracket(char* arr)
{
	Stk stktmp;
	StackInit(&stktmp);
	StackPush(&stktmp, ' ');//可删
	char* cur = arr;
	while (*cur != '\0')
	{
		if (*cur == '(' || *cur == '[' || *cur == '{')
		{
			StackPush(&stktmp, *cur);
		}
		else if (*cur == ')' || *cur == ']' || *cur == '}')//可简化
		{
			if (StackTop(&stktmp) != ((*cur)-1)&& StackTop(&stktmp) != ((*cur) - 2))
			{
				StackDestroy(&stktmp);//提前返回也要释放临时内存防止泄露
				return false;
			}
			StackPop(&stktmp);
		}
		cur++;
	}
	
	if (StackTop(&stktmp) != ' ')//保证不对称括号也可判断
	{
		StackDestroy(&stktmp);//提前返回也要释放临时内存防止泄露
		return false;
	}
	StackDestroy(&stktmp);
	return true;
}
/*OJ题-有效的括号判断-测试用例*/void JudgeTest()
{
	printf("****OJ题测试用例开始*******************\n");
	char str[] = "{[()]{}}";//
	printf("str = %s\n", str);
	printf("JudgeRet = %d\n",JudgeBracket(str));
	printf("****OJ题测试用例结束*******************\n\n");

}


//【笔记】
//【初阶】44.1 双向链表收尾
	//链表和顺序表两者各有优劣，严格来说两者相辅相成
	//顺序表：
	// 优点1：支持随机访问，可以实现快排qsort、二分查找等
	// 优点2：CPU高速缓存的利用率高
	// 缺点1：头部、中部插入时间效率低
	// 缺点2：物理空间连续，空间不足需要增容，增容时消耗时间和空间
	//链表（双向带头循环）：
	// 优点1：任意位置插入、删除效率高
	// 优点2：可按需申请释放空间
	// 缺点1：不支持随机访问，即利用下标访问，快排qsort、二分查找等算法不适用
	// 缺点2：每个节点都需要存储指针，消耗一定内存
	// 缺点3：CPU高速缓存命中率低
//【初阶】44.2 栈和队列
	//栈是一种特殊的线性表，只允许在固定一端进行插入和删除元素的操作
	// 插入和删除的一端叫做栈顶，另一端叫做栈底，后进先出或先进后出，可以理解为弹匣的结构
	// 用顺序表和链表都可实现栈，顺序表适合尾插尾删，尾部做栈顶；单链表适合头插头删，头部做栈顶
	// 相比之下顺序表实现链表更优 
